#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    method_map = [list.append, list.insert]

    def zigzagLevelOrder(self, root):
        # DFS
        self.ret = []
        self.rec_dfs_level_order(root, 0)

        return self.ret

    def rec_dfs_level_order(self, node, depth):
        if node is None:
            return

        print(depth)

        if len(self.ret) <= depth:
            assert len(self.ret) == depth
            self.ret.append([])

        if depth % 2 == 0:
            self.ret[depth].append(node.val)
        elif depth % 2 == 1:
            self.ret[depth].insert(0, node.val)
            # self.ret[depth].append(node.val)
        else:
            assert False

        self.rec_dfs_level_order(node.left, depth+1)
        self.rec_dfs_level_order(node.right, depth+1)


def main():
    print("start main")

    n1 = TreeNode(1)
    n2 = TreeNode(2)
    root = TreeNode(0)
    # root.left = None
    root.right = n1
    root.left = n2

    s = Solution()
    ret = s.zigzagLevelOrder(root)
    print(ret)

if __name__ == "__main__":
    main()
